//题目:
// 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
// 例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

// 示例 1：
// 输入：n = 12
// 输出：3 
// 解释：12 = 4 + 4 + 4

// 示例 2：
// 输入：n = 13
// 输出：2
// 解释：13 = 4 + 9

#include<iostream>
#include<vector>

using namespace std;

//代码:
class Solution 
{
    vector<int> v_square;
public:
    int numSquares(int n) 
    {
        //记录10000以内的所有完全平方数
        for(int i=1;i*i<=10000;i++)
            v_square.push_back(i*i);
        //1.创建dp表————dp[i][j]表示：选第i个元素，和为j时，选中的完全平方数的最少数量
        // int sz=v_square.size();
        // vector<vector<int>> dp(sz+1,vector<int>(n+1,0x3f3f3f3f));
        // //2.初始化
        // dp[0][0]=0; //这一步，至关重要！！这里的dp[0][0]是有实际意义的
        // //3.动态转移方程:dp[i][j]=min(dp[i-1][j],dp[i][j-v_square[i-1]])
        // for(int i=1;i<=sz;i++)
        // {
        //     for(int j=0;j<=n;j++)
        //     {
                   // 暴力遍历————超时
        //         // for(int k=0;k*nums[i-1]<=j;k++)
        //         //     dp[i][j]=min(dp[i][j],dp[i-1][j-k*nums[i-1]]+k);

        //         dp[i][j]=dp[i-1][j];
        //         if(j-v_square[i-1]>=0)
        //             dp[i][j]=min(dp[i][j],dp[i][j-v_square[i-1]]+1);
        //     }
        // }
        // //4.确定返回值
        // return dp[sz][n];

        //空间优化
        int sz=v_square.size();
        vector<int> dp(n+1,0x3f3f3f3f);
        //2.初始化
        dp[0]=0;
        //3.动态转移方程:dp[i][j]=min(dp[i-1][j],dp[i][j-v_square[i-1]])
        for(int i=1;i<=sz;i++)
            for(int j=v_square[i-1];j<=n;j++)
                dp[j]=min(dp[j],dp[j-v_square[i-1]]+1);

        //4.确定返回值
        return dp[n];
    }
};